#include <iostream>



template<typename T>
struct avl{  //平衡二叉树的结构
    avl* left;
    avl* right;
    int height;
    T value;
    

    //初始化了列表在开始前就执行了
    avl()：left(NULL), right(NULL), height(-1), value(T()){
        left = NULL;
        right = NULL;
        height = -1;
        value = T();
    }
};

template<typename T>
class AvlTree{
    public:
    typedef avl<T*> 

    public:
        void leftroration(PNode root){
            PNode tmp = root->right;
            root->right = tmp->left;
            tmp->left = root;
            root->height = max(height(root->left), height(root->right)) + 1;
            tmp->height = max(height(tmp->left), height(tmp->right)) + 1;
            root = tmp;
        }
        }


        int getHeight(PNode root){
            if(!root){
                return -1;
            }
            return max(getHeight(root->left), getHeight(root->right)) + 1;   
        }
        

        void rightrotation(PNode root){
            PNode tmp = root->left;
            root->left = tmp->right;    
            tmp->right = root;
            root->height = max(height(root->left), height(root->right)) + 1;
            tmp->height = max(height(tmp->left), height(tmp->right)) + 1;
            root = tmp;
        }

        void insert(const T& value){
            if(!root){
                root = new PNode(value)
            }
        }

    private:
        PNode  root;
};
